package com.chocho.link;

import java.util.Stack;

public class LinkListDemo {
    public static void main(String[] args) {
        //创建单链表
        LinkList list = new LinkList();
        list.add(1);
        list.add(2);

//        list.list();

        //删除元素
        list.delete(1);
//        list.list();

        //更新元素
        list.update(1, 666);
//        list.list();

        //查找第一个元素
//        System.out.println(list.get(1));

        //常见面试题
        //1.单链表节点个数
        LinkList listA = new LinkList();
        listA.add(1);
        listA.add(2);
        listA.add(3);
        listA.add(4);
        System.out.printf("单链表节点个数:%d\n", listA.getLength());

        //2.查找单链表倒数第k个节点
        int k = 5;
        Node node = listA.findLastIndexNode(k);
        if(node != null) {
            System.out.printf("查找单链表倒数第%d个节点:%d\n", k, node.getData());
        }

        //3.链表反转
        LinkList listB = new LinkList();
        listB.add(11);
        listB.add(10);
        listB.add(9);
        listB.add(8);
        System.out.printf("链表反转:\n");
        listB.reverse();
        listB.list();

        //4.逆序打印链表
        System.out.printf("\n逆序打印链表:\n");
        listB.reversePrint();

        //5.合并有序链表
        Node headC = mergeList(listA.head, listB.head);
        LinkList listC = new LinkList();
        listC.head = headC;
        System.out.printf("\n合并有序链表:\n");
        listC.list();
    }

    /**
     * 合并两个有序链表
     * @param a
     * @param b
     * @return
     */
    public static Node mergeList(Node a, Node b){
        Node head = new Node(0, null);
        Node temp = head;
        Node tempA = a.getNext();
        Node tempB = b.getNext();
        while(tempA != null && tempB != null){
            if(tempA.getData() <= tempB.getData()){
                temp.setNext(tempA);
                tempA = tempA.getNext();
                temp = temp.getNext();
            }else{
                temp.setNext(tempB);
                tempB = tempB.getNext();
                temp = temp.getNext();
            }
        }

        while(tempA != null){
            temp.setNext(tempA);
            tempA = tempA.getNext();
            temp = temp.getNext();
        }

        while(tempB != null){
            temp.setNext(tempB);
            tempB = tempB.getNext();
            temp = temp.getNext();
        }

        return head;
    }
}

/**
 * 带头节点的单链表
 */
class LinkList{
    public Node head = new Node(0, null);

    /**
     * 新增数据到单链表
     * @param data
     */
    public void add(int data){
        Node temp = head;
        //遍历到链表尾部
        while(temp.getNext() != null){
            temp = temp.getNext();
        }

        //新增数据，将数据添加到链表末尾
        Node node = new Node(data, null);
        temp.setNext(node);
    }

    /**
     * 遍历链表
     */
    public void list(){
        Node temp = head;
        while(temp.getNext() != null){
            temp = temp.getNext();
            System.out.printf("%d->", temp.getData());
        }
        System.out.printf("NULL\n");
    }

    /**
     * 删除链表中元素
     */
    public void delete(int i){
        Node temp = head;
        int count = 1;
        //遍历链表，找到元素位置
        while(temp.getNext() != null && count != i){
            count++;
            temp = temp.getNext();
        }

        //删除数据
        temp.setNext(temp.getNext().getNext());
    }

    /**
     * 修改链表中元素
     * @param i
     * @param newData
     */
    public void update(int i, int newData){
        Node temp = head;
        int count = 1;
        //遍历链表，找到元素位置
        while(temp.getNext() != null && count != i){
            count++;
            temp = temp.getNext();
        }

        //更新元素值
        temp.getNext().setData(newData);
    }

    /**
     * 查找元素
     */
    public int get(int i){
        Node temp = head;
        int count = 1;
        //遍历链表，找到元素位置
        while(temp.getNext() != null && count != i){
            count++;
            temp = temp.getNext();
        }

        //返回元素值
        return temp.getNext().getData();
    }

    /**
     *获取单链表中节点的个数
     * @return
     */
    public int getLength(){
        Node temp = head;
        int count = 0;
        //遍历链表，找到元素位置
        while(temp.getNext() != null){
            count++;
            temp = temp.getNext();
        }

        return count;
    }

    /**
     * 获取倒数第k个节点
     * @param k
     * @return
     */
    public Node findLastIndexNode(int k){
        if(k < 0){
            System.out.println("k 不能为负数");
            return null;
        }
        if(k > getLength()){
            k = k % (getLength() + 1);
        }

        //遍历到size-k的数据
        Node temp = head;
        if(temp.getNext() == null){
            return null;
        }

        int count = getLength() - k;
        //遍历链表，找到元素位置
        while(temp.getNext() != null && count >= 0){
            count--;
            temp = temp.getNext();
        }

        return temp;
    }

    /**
     * 单链表反转
     * @return
     */
    public void reverse(){
        //链表判空 || 只要一个节点，以上情况不需要反转
        if(getLength() == 0 || getLength() == 1){
            return;
        }

        //用于遍历链表
        Node cur = head.getNext();
        //用于记录当前指针的下一个节点，防止断链
        Node next = null;
        //新增链表
        Node newHead = new Node(0, null);

        //遍历原来的链表
        while(cur != null){
            //保存当前指针的下一个节点
            next = cur.getNext();
            //链表反转 将当前节点头插到新链表
            cur.setNext(newHead.getNext());
            newHead.setNext(cur);
            cur = next; //恢复到原来的遍历
        }

        //将新链表替换反转前链表
        head.setNext(newHead.getNext());
    }

    /**
     * 逆序打印链表
     */
    public void reversePrint(){
        //使用栈：先进后出的顺序，实现反转
        Stack<Integer> stack = new Stack<>();
        //先进
        Node temp = head;
        //遍历链表，找到元素位置
        while(temp.getNext() != null){
            temp = temp.getNext();
            stack.push(temp.getData());
        }

        //后出
        while(stack.size() > 0){
            System.out.printf("%d->", stack.pop());
        }
        System.out.printf("NULL");
    }
}
